home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / croutes.zip / SQ.C86 < prev    next >
Text File  |  1984-07-29  |  22KB  |  778 lines
  1. /*% cc -O -n % -o sq
  2. */
  3. #include <stdio.h>
  4. #define TRUE 1
  5. #define rewind(c) fseek(c,0L,0);                       /* 1.7 */
  6. #define FALSE 0
  7. #define ERROR (-1)
  8. #define PATHLEN 312    /* Number of characters allowed in pathname */
  9. #define ALTNAME "sq.out"
  10.  
  11. /* Definitions and external declarations */
  12. #define RECOGNIZE 0xFF76    /* unlikely pattern */
  13. /* *** Stuff for first translation module *** */
  14. #define DLE 0x90
  15.  
  16.  
  17. /* *** Stuff for second translation module *** */
  18. #define SPEOF 256    /* special endfile token */
  19. #define NUMVALS 257    /* 256 data values plus SPEOF*/
  20. /* Definitions and external declarations */
  21. int Usestd;    /* Use stdout for squeezed output */
  22. unsigned crc;    /* error check code */
  23. /* *** Stuff for first translation module *** */
  24. int likect;    /*count of consecutive identical chars */
  25. int lastchar, newchar;
  26. char state;
  27. /* states */
  28. #define NOHIST    0    /*don't consider previous input*/
  29. #define SENTCHAR 1    /*lastchar set, no lookahead yet */
  30. #define SENDNEWC 2    /*newchar set, previous sequence done */
  31. #define SENDCNT 3    /*newchar set, DLE sent, send count next */
  32.  
  33. /* *** Stuff for second translation module *** */
  34. #define NOCHILD -1    /* indicates end of path through tree */
  35. #define NUMNODES (NUMVALS + NUMVALS - 1)    /* nbr of nodes */
  36.  
  37. #define MAXCOUNT 65535    /* biggest unsigned integer */
  38.  
  39. /* The following array of structures are the nodes of the
  40.  * binary trees. The first NUMVALS nodes becomethe leaves of the
  41.  * final tree and represent the values of the data bytes being
  42.  * encoded and the special endfile, SPEOF.
  43.  * The remaining nodes become the internal nodes of the final tree.
  44.  */
  45.  
  46. struct    nd {
  47.     unsigned weight;    /* number of appearances */
  48.     int tdepth;        /* length on longest path in tre*/
  49.     int lchild, rchild;    /* indexes to next level */
  50. }
  51. node[NUMNODES];
  52.  
  53. int dctreehd;    /*index to head node of final tree */
  54.  
  55. /* This is the encoding table:
  56.  * The bit strings have first bit in  low bit.
  57.  * Note that counts were scaled so code fits unsigned integer
  58.  */
  59.  
  60. int codelen[NUMVALS];        /* number of bits in code */
  61. unsigned code[NUMVALS];     /* code itself, right adjusted */
  62. unsigned tcode;         /* temporary code value */
  63.  
  64.  
  65. /* Variables used by encoding process */
  66. int curin;    /* Value currently being encoded */
  67. int cbitsrem;    /* Number of code string bits remaining */
  68. unsigned ccode; /* Current code shifted so next code bit is at right */
  69. /* This program compresses a file without losing information.
  70.  * The usq.com program is required to unsqueeze the file
  71.  * before it can be used.
  72.  *
  73.  * Typical compression rates are:
  74.  *    .COM    6%    (Don't bother)
  75.  *    .ASM    33%    (using full ASCII set)
  76.  *    .DIC    46%    (using only uppercase and a few others)
  77.  * Squeezing a really big file takes a few minutes.
  78.  *
  79.  * Useage:
  80.  *    sq file ...
  81.  *
  82.  *
  83.  * The squeezed file name is formed by changing the second from last
  84.  * letter of the file type to Q. If there is no file type,
  85.  * the squeezed file type is QQQ. If the name exists it is
  86.  * overwritten!
  87.  *
  88.  * The transformations compress strings of identical bytes and
  89.  * then encode each resulting byte value and EOF as bit strings
  90.  * having lengths in inverse proportion to their frequency of
  91.  * occurrance in the intermediate input stream. The latter uses
  92.  * the Huffman algorithm. Decoding information is included in
  93.  * the squeezed file, so squeezing short files or files with
  94.  * uniformly distributed byte values will actually increase size.
  95.  */
  96.  
  97. /* CHANGE HISTORY:
  98.  * 1.5u **nix version - means output to stdout.
  99.  *  (stdin not allowed becuase sq needs to rewind input, which
  100.  *  won't work with pipes.)
  101.  * Filename generation changed to suit **nix and stdio.
  102.  * 1.6u machine independent output for file compatibility with
  103.  *    original CP/M version SQ, when running on machine with
  104.  *    IBM byte ordering such as Z8000 and 68000.
  105.  *
  106.  * 1.7    08/13/83  C86 Version by Wayne Fruhwald
  107.  *    Converted to work with Computer Innovation's C86 c compiler under MSDOS.
  108.  *
  109.  */
  110.  
  111. #define VERSION "1.7    8-13-83"                                       /* 1.7 */
  112.  
  113. main(argc, argv)
  114. int argc;
  115. char *argv[];
  116. {
  117.     register i,c;
  118.  
  119.  
  120.     /* Process the parameters in order */
  121.     for(i = 1; i < argc; ++i) {
  122.         if(strcmp(argv[i], "-")==0)
  123.             Usestd = TRUE;
  124.     }
  125.     for(i = 1; i < argc; ++i) {
  126.         if(strcmp(argv[i], "-")!=0)
  127.             obey(argv[i]);
  128.     }
  129.  
  130.     if(argc < 2) {
  131.         fprintf(stderr,"File squeezer version %s by\n\tRichard Greenlaw\n\t251 Colony Ct.\n\tGahanna, Ohio 43230\n", VERSION);
  132.         fprintf(stderr, "Usage: sq [-] pathname ...\n");
  133.         fprintf(stderr, "\t- squeezed output to stdout\n");
  134.         exit(1);
  135.     }
  136.     exit(0);
  137. }
  138.  
  139. obey(p)
  140. char *p;
  141. {
  142.     char *w,*q;
  143.     char outfile[PATHLEN+2];    /* output file spec. */
  144.  
  145.     /* First build output file name */
  146.  
  147.     strcpy(outfile, p);
  148.     /* Find and change output file type */
  149.     for(w=q = outfile; *q != '\0'; ++q)     /* skip leading /'s */
  150.         if( *q == '/')
  151.             w = q+1;
  152.     for(q = w; *q != '\0'; ++q)
  153.         if(*q == '.')
  154.             if(*(q + 1) == '\0')
  155.                 *q = '\0';      /* kill trailing dot */
  156.             else
  157.                 switch(*(q+2)) {
  158.                 case 'q':
  159.                 case 'Q':
  160.                     fprintf(stderr, "\n%s ignored ( already squeezed?)", p);
  161.                     return;
  162.                 case '\0':
  163.                     *(q+3) = '\0';
  164.                     /* fall thru */
  165.                 default:
  166.                     *(q + 2) = 'Q';
  167.                     goto named;
  168.                 }
  169.     /* No file type */
  170.     strcat(outfile, ".QQQ");
  171. named:
  172.     if(strlen(w)>14)
  173.         strcpy(outfile, ALTNAME);    /* check for too long name */
  174.     squeeze(p, outfile);
  175. }
  176.  
  177. squeeze(infile, outfile)
  178. char *infile, *outfile;
  179. {
  180.     register i, c;
  181.     FILE *inbuff, *outbuff; /* file buffers */
  182.  
  183.     fprintf(stderr, "\n%s -> %s: ", infile, outfile);
  184.  
  185.     if((inbuff=fopen(infile, "rb")) == NULL) {                     /* 1.7 */
  186.         fprintf(stderr, "Can't open %s for input pass 1\n", infile);
  187.         return;
  188.     }
  189.     if(Usestd)
  190.         outbuff=stdout;
  191.     else if((outbuff=fopen(outfile, "wb")) == NULL) {              /* 1.7 */
  192.         fprintf(stderr, "Can't create %s\n", outfile);
  193.         fclose(inbuff);
  194.         return;
  195.     }
  196.  
  197.     /* First pass - get properties of file */
  198.     crc = 0;    /* initialize checksum */
  199.     fprintf(stderr, "analyzing, ");
  200.     init_ncr();
  201.     init_huff(inbuff);
  202.     rewind(inbuff);
  203.     /* Write output file header with decoding info */
  204.     wrt_head(outbuff, infile);
  205.  
  206.     /* Second pass - encode the file */
  207.     fprintf(stderr, "squeezing, ");
  208.  
  209.     init_ncr();    /* For second pass */
  210.  
  211.     /* Translate the input file into the output file */
  212.     while((c = gethuff(inbuff)) != EOF)
  213.         if(putc(c, outbuff) == ERROR && ferror(outbuff)) {
  214.             fprintf(stderr, "ERROR - write failure in %s\n", outfile);
  215.             goto closeall;
  216.         }
  217.     fprintf(stderr, " done.\n");
  218. closeall:
  219.     fclose(inbuff);
  220. closeout:
  221.     fflush(outbuff);
  222.     fclose(outbuff);
  223. }
  224.  
  225.  
  226. /* First translation - encoding of repeated characters
  227.  * The code is byte for byte pass through except that
  228.  * DLE is encoded as DLE, zero and repeated byte values
  229.  * are encoded as value, DLE, count for count >= 3.
  230.  */
  231.  
  232. init_ncr()    /*initialize getcnr() */
  233. {
  234.     state = NOHIST;
  235. }
  236.  
  237. int
  238. getcnr(iob)
  239. FILE *iob;
  240. {
  241.     switch(state) {
  242.     case NOHIST:
  243.         /* No relevant history */
  244.         state = SENTCHAR;
  245.         return lastchar = getc_crc(iob);
  246.     case SENTCHAR:
  247.         /* Lastchar is set, need lookahead */
  248.         switch(lastchar) {
  249.         case DLE:
  250.             state = NOHIST;
  251.             return 0;    /* indicates DLE was the data */
  252.         case EOF:
  253.             return EOF;
  254.         default:
  255.             for(likect = 1; (newchar = getc_crc(iob)) == lastchar && likect < 255; ++likect)
  256.                 ;
  257.             switch(likect) {
  258.             case 1:
  259.                 return lastchar = newchar;
  260.             case 2:
  261.                 /* just pass through */
  262.                 state = SENDNEWC;
  263.                 return lastchar;
  264.             default:
  265.                 state = SENDCNT;
  266.                 return DLE;
  267.             }
  268.         }
  269.     case SENDNEWC:
  270.         /* Previous sequence complete, newchar set */
  271.         state = SENTCHAR;
  272.         return lastchar = newchar;
  273.     case SENDCNT:
  274.         /* Sent DLE for repeat sequence, send count */
  275.         state = SENDNEWC;
  276.         return likect;
  277.     default:
  278.         fprintf(stderr,"Bug - bad state\n");
  279.         exit(1);
  280.         /* NOTREACHED */
  281.     }
  282. }
  283.  
  284.  
  285. /******** Second translation - bytes to variable length bit strings *********/
  286.  
  287.  
  288. /* This translation uses the Huffman algorithm to develop a
  289.  * binary tree representing the decoding information for
  290.  * a variable length bit string code for each input value.
  291.  * Each string's length is in inverse proportion to its
  292.  * frequency of appearance in the incoming data stream.
  293.  * The encoding table is derived from the decoding table.
  294.  *
  295.  * The range of valid values into the Huffman algorithm are
  296.  * the values of a byte stored in an integer plus the special
  297.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  298.  *
  299.  * The "node" array of structures contains the nodes of the
  300.  * binary tree. The first NUMVALS nodes are the leaves of the
  301.  * tree and represent the values of the data bytes being
  302.  * encoded and the special endfile, SPEOF.
  303.  * The remaining nodes become the internal nodes of the tree.
  304.  *
  305.  * In the original design it was believed that
  306.  * a Huffman code would fit in the same number of
  307.  * bits that will hold the sum of all the counts.
  308.  * That was disproven by a user's file and was a rare but
  309.  * infamous bug. This version attempts to choose among equally
  310.  * weighted subtrees according to their maximum depths to avoid
  311.  * unnecessarily long codes. In case that is not sufficient
  312.  * to guarantee codes <= 16 bits long, we initially scale
  313.  * the counts so the total fits in an unsigned integer, but
  314.  * if codes longer than 16 bits are generated the counts are
  315.  * rescaled to a lower ceiling and code generation is retried.
  316.  */
  317.  
  318. /* Initialize the Huffman translation. This requires reading
  319.  * the input file through any preceding translation functions
  320.  * to get the frequency distribution of the various values.
  321.  */
  322.  
  323. init_huff(ib)
  324. FILE *ib;
  325. {
  326.     register c, i;
  327.     int btlist[NUMVALS];    /* list of intermediate binary trees */
  328.     int listlen;        /* length of btlist */
  329.     unsigned *wp;        /* simplifies weight counting */
  330.     unsigned ceiling;    /* limit for scaling */
  331.  
  332.     /* Initialize tree nodes to no weight, no children */
  333.     init_tree();
  334.  
  335.     /* Build frequency info in tree */
  336.     do {
  337.         c = getcnr(ib);
  338.         if(c == EOF)
  339.             c = SPEOF;
  340.         if(*(wp = &node[c].weight) !=  MAXCOUNT)
  341.             ++(*wp);
  342.     }
  343.     while(c != SPEOF);
  344.  
  345.     ceiling = MAXCOUNT;
  346.  
  347.     do {    /* Keep trying to scale and encode */
  348.         if(ceiling != MAXCOUNT)
  349.             fprintf(stderr, "*** rescaling ***, ");
  350.         scale(ceiling);
  351.         ceiling /= 2;    /* in case we rescale */
  352.  
  353.         /* Build list of single node binary trees having
  354.                  * leaves for the input values with non-zero counts
  355.                  */
  356.         for(i = listlen = 0; i < NUMVALS; ++i)
  357.             if(node[i].weight != 0) {
  358.                 node[i].tdepth = 0;
  359.                 btlist[listlen++] = i;
  360.             }
  361.  
  362.         /* Arrange list of trees into a heap with the entry
  363.                  * indexing the node with the least weight at the top.
  364.                  */
  365.         heap(btlist, listlen);
  366.  
  367.         /* Convert the list of trees to a single decoding tree */
  368.         bld_tree(btlist, listlen);
  369.  
  370.         /* Initialize the encoding table */
  371.         init_enc();
  372.  
  373.         /* Try to build encoding table.
  374.                  * Fail if any code is > 16 bits long.
  375.                  */
  376.     }
  377.     while(buildenc(0, dctreehd) == ERROR);
  378.  
  379.     /* Initialize encoding variables */
  380.     cbitsrem = 0;    /*force initial read */
  381.     curin = 0;    /*anything but endfile*/
  382. }
  383.  
  384. /* The count of number of occurrances of each input value
  385.  * have already been prevented from exceeding MAXCOUNT.
  386.  * Now we must scale them so that their sum doesn't exceed
  387.  * ceiling and yet no non-zero count can become zero.
  388.  * This scaling prevents errors in the weights of the
  389.  * interior nodes of the Huffman tree and also ensures that
  390.  * the codes will fit in an unsigned integer. Rescaling is
  391.  * used if necessary to limit the code length.
  392.  */
  393.  
  394. scale(ceil)
  395. unsigned ceil;    /* upper limit on total weight */
  396. {
  397.     register i,c;
  398.     int ovflw, divisor;
  399.     unsigned w, sum;
  400.     char increased;     /* flag */
  401.  
  402.     do {
  403.         for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  404.             if(node[i].weight > (ceil - sum))
  405.                 ++ovflw;
  406.             sum += node[i].weight;
  407.         }
  408.  
  409.         divisor = ovflw + 1;
  410.  
  411.         /* Ensure no non-zero values are lost */
  412.         increased = FALSE;
  413.         for(i = 0; i < NUMVALS; ++i) {
  414.             w = node[i].weight;
  415.             if (w < divisor && w != 0) {
  416.                 /* Don't fail to provide a code if it's used at all */
  417.                 node[i].weight = divisor;
  418.                 increased = TRUE;
  419.             }
  420.         }
  421.     }
  422.     while(increased);
  423.  
  424.     /* Scaling factor choosen, now scale */
  425.     if(divisor > 1)
  426.         for(i = 0; i < NUMVALS; ++i)
  427.             node[i].weight /= divisor;
  428. }
  429.  
  430. /* heap() and adjust() maintain a list of binary trees as a
  431.  * heap with the top indexing the binary tree on the list
  432.  * which has the least weight or, in case of equal weights,
  433.  * least depth in its longest path. The depth part is not
  434.  * strictly necessary, but tends to avoid long codes which
  435.  * might provoke rescaling.
  436.  */
  437.  
  438. heap(list, length)
  439. int list[], length;
  440. {
  441.     register i;
  442.  
  443.     for(i = (length - 2) / 2; i >= 0; --i)
  444.         adjust(list, i, length - 1);
  445. }
  446.  
  447. /* Make a heap from a heap with a new top */
  448.  
  449. adjust(list, top, bottom)
  450. int list[], top, bottom;
  451. {
  452.     register k, temp;
  453.  
  454.     k = 2 * top + 1;    /* left child of top */
  455.     temp = list[top];    /* remember root node of top tree */
  456.     if( k <= bottom) {
  457.         if( k < bottom && cmptrees(list[k], list[k + 1]))
  458.             ++k;
  459.  
  460.         /* k indexes "smaller" child (in heap of trees) of top */
  461.         /* now make top index "smaller" of old top and smallest child */
  462.         if(cmptrees(temp, list[k])) {
  463.             list[top] = list[k];
  464.             list[k] = temp;
  465.             /* Make the changed list a heap */
  466.             adjust(list, k, bottom); /*recursive*/
  467.         }
  468.     }
  469. }
  470.  
  471. /* Compare two trees, if a > b return true, else return false
  472.  * note comparison rules in previous comments.
  473.  */
  474.  
  475. cmptrees(a, b)
  476. register int a, b;  /* root nodes of trees */
  477. {
  478.     if(node[a].weight > node[b].weight)
  479.         return TRUE;
  480.     if(node[a].weight == node[b].weight)
  481.         if(node[a].tdepth > node[b].tdepth)
  482.             return TRUE;
  483.     return FALSE;
  484. }
  485.  
  486. /* HUFFMAN ALGORITHM: develops the single element trees
  487.  * into a single binary tree by forming subtrees rooted in
  488.  * interior nodes having weights equal to the sum of weights of all
  489.  * their descendents and having depth counts indicating the
  490.  * depth of their longest paths.
  491.  *
  492.  * When all trees have been formed into a single tree satisfying
  493.  * the heap property (on weight, with depth as a tie breaker)
  494.  * then the binary code assigned to a leaf (value to be encoded)
  495.  * is then the series of left (0) and right (1)
  496.  * paths leading from the root to the leaf.
  497.  * Note that trees are removed from the heaped list by
  498.  * moving the last element over the top element and
  499.  * reheaping the shorter list.
  500.  */
  501.  
  502. bld_tree(list, len)
  503. int list[];
  504. int len;
  505. {
  506.     register freenode;        /* next free node in tree */
  507.     register struct nd *frnp;    /* free node pointer */
  508.     int lch, rch;        /* temporaries for left, right children */
  509.     int i;
  510.  
  511.     /* Initialize index to next available (non-leaf) node.
  512.          * Lower numbered nodes correspond to leaves (data values).
  513.          */
  514.     freenode = NUMVALS;
  515.  
  516.     while(len > 1) {
  517.         /* Take from list two btrees with least weight
  518.                  * and build an interior node pointing to them.
  519.                  * This forms a new tree.
  520.                  */
  521.         lch = list[0];    /* This one will be left child */
  522.  
  523.         /* delete top (least) tree from the list of trees */
  524.         list[0] = list[--len];
  525.         adjust(list, 0, len - 1);
  526.  
  527.         /* Take new top (least) tree. Reuse list slot later */
  528.         rch = list[0];    /* This one will be right child */
  529.  
  530.         /* Form new tree from the two least trees using
  531.                  * a free node as root. Put the new tree in the list.
  532.                  */
  533.         frnp = &node[freenode]; /* address of next free node */
  534.         list[0] = freenode++;    /* put at top for now */
  535.         frnp->lchild = lch;
  536.         frnp->rchild = rch;
  537.         frnp->weight = node[lch].weight + node[rch].weight;
  538.         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  539.         /* reheap list    to get least tree at top*/
  540.         adjust(list, 0, len - 1);
  541.     }
  542.     dctreehd = list[0];    /*head of final tree */
  543. }
  544.  
  545. /* ???????????? */
  546. maxchar(a, b)
  547. {
  548.     return a > b ? a : b;
  549. }
  550. /* Initialize all nodes to single element binary trees
  551.  * with zero weight and depth.
  552.  */
  553.  
  554. init_tree()
  555. {
  556.     register i;
  557.  
  558.     for(i = 0; i < NUMNODES; ++i) {
  559.         node[i].weight = 0;
  560.         node[i].tdepth = 0;
  561.         node[i].lchild = NOCHILD;
  562.         node[i].rchild = NOCHILD;
  563.     }
  564. }
  565.  
  566. init_enc()
  567. {
  568.     register i;
  569.  
  570.     /* Initialize encoding table */
  571.     for(i = 0; i < NUMVALS; ++i) {
  572.         codelen[i] = 0;
  573.     }
  574. }
  575.  
  576. /* Recursive routine to walk the indicated subtree and level
  577.  * and maintain the current path code in bstree. When a leaf
  578.  * is found the entire code string and length are put into
  579.  * the encoding table entry for the leaf's data value.
  580.  *
  581.  * Returns ERROR if codes are too long.
  582.  */
  583.  
  584. int        /* returns ERROR or NULL */
  585. buildenc(level, root)
  586. int level;/* level of tree being examined, from zero */
  587. int root; /* root of subtree is also data value if leaf */
  588. {
  589.     register l, r;
  590.  
  591.     l = node[root].lchild;
  592.     r = node[root].rchild;
  593.  
  594.     if( l == NOCHILD && r == NOCHILD) {
  595.         /* Leaf. Previous path determines bit string
  596.                  * code of length level (bits 0 to level - 1).
  597.                  * Ensures unused code bits are zero.
  598.                  */
  599.         codelen[root] = level;
  600.         code[root] = tcode & (((unsigned)~0) >> (16 - level));
  601.         return (level > 16) ? ERROR : NULL;
  602.     }
  603.     else {
  604.         if( l != NOCHILD) {
  605.             /* Clear path bit and continue deeper */
  606.             tcode &= ~(1 << level);
  607.             /* NOTE RECURSION */
  608.             if(buildenc(level + 1, l) == ERROR)
  609.                 return ERROR;
  610.         }
  611.         if(r != NOCHILD) {
  612.             /* Set path bit and continue deeper */
  613.             tcode |= 1 << level;
  614.             /* NOTE RECURSION */
  615.             if(buildenc(level + 1, r) == ERROR)
  616.                 return ERROR;
  617.         }
  618.     }
  619.     return NULL;    /* if we got here we're ok so far */
  620. }
  621.  
  622. /* Write out the header of the compressed file */
  623.  
  624. wrt_head(ob, infile)
  625. FILE *ob;
  626. char *infile;    /* input file name (w/ or w/o drive) */
  627. {
  628.     register l,r;
  629.     int i, k;
  630.     int numnodes;        /* nbr of nodes in simplified tree */
  631.  
  632.     putwe(RECOGNIZE, ob);    /* identifies as compressed */
  633.     putwe(crc, ob);     /* unsigned sum of original data */
  634.  
  635.     /* Record the original file name w/o drive */
  636.     if(*(infile + 1) == ':')
  637.         infile += 2;    /* skip drive */
  638.  
  639.     do {
  640.         putce(*infile, ob);
  641.     }
  642.     while(*(infile++) != '\0');
  643.  
  644.  
  645.     /* Write out a simplified decoding tree. Only the interior
  646.          * nodes are written. When a child is a leaf index
  647.          * (representing a data value) it is recoded as
  648.          * -(index + 1) to distinguish it from interior indexes
  649.          * which are recoded as positive indexes in the new tree.
  650.          * Note that this tree will be empty for an empty file.
  651.          */
  652.  
  653.     numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
  654.     putwe(numnodes, ob);
  655.  
  656.     for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
  657.         l = node[i].lchild;
  658.         r = node[i].rchild;
  659.         l = l < NUMVALS ? -(l + 1) : dctreehd - l;
  660.         r = r < NUMVALS ? -(r + 1) : dctreehd - r;
  661.         putwe(l, ob);    /* left child */
  662.         putwe(r, ob);    /* right child */
  663.     }
  664. }
  665.  
  666. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  667.  *
  668.  * There are two unsynchronized bit-byte relationships here.
  669.  * The input stream bytes are converted to bit strings of
  670.  * various lengths via the static variables named c...
  671.  * These bit strings are concatenated without padding to
  672.  * become the stream of encoded result bytes, which this
  673.  * function returns one at a time. The EOF (end of file) is
  674.  * converted to SPEOF for convenience and encoded like any
  675.  * other input value. True EOF is returned after that.
  676.  *
  677.  * The original gethuff() called a seperate function,
  678.  * getbit(), but that more readable version was too slow.
  679.  */
  680.  
  681. int        /*  Returns byte values except for EOF */
  682. gethuff(ib)
  683. FILE *ib;
  684. {
  685.     int rbyte;    /* Result byte value */
  686.     int need, take; /* numbers of bits */
  687.  
  688.     rbyte = 0;
  689.     need = 8;    /* build one byte per call */
  690.  
  691.     /* Loop to build a byte of encoded data
  692.          * Initialization forces read the first time
  693.          */
  694.  
  695. loop:
  696.     if(cbitsrem >= need) {
  697.         /* Current code fullfills our needs */
  698.         if(need == 0)
  699.             return rbyte;
  700.         /* Take what we need */
  701.         rbyte |= ccode << (8 - need);
  702.         /* And leave the rest */
  703.         ccode >>= need;
  704.         cbitsrem -= need;
  705.         return rbyte;
  706.     }
  707.  
  708.     /* We need more than current code */
  709.     if(cbitsrem > 0) {
  710.         /* Take what there is */
  711.         rbyte |= ccode << (8 - need);
  712.         need -= cbitsrem;
  713.     }
  714.     /* No more bits in current code string */
  715.     if(curin == SPEOF) {
  716.         /* The end of file token has been encoded. If
  717.                  * result byte has data return it and do EOF next time
  718.                  */
  719.         cbitsrem = 0;
  720.  
  721.         /*NOTE: +0 is to fight compiler bug? */
  722.         return (need == 8) ? EOF : rbyte + 0;
  723.     }
  724.  
  725.     /* Get an input byte */
  726.     if((curin = getcnr(ib)) == EOF)
  727.         curin = SPEOF;    /* convenient for encoding */
  728.  
  729.     /* Get the new byte's code */
  730.     ccode = code[curin];
  731.     cbitsrem = codelen[curin];
  732.  
  733.     goto loop;
  734. }
  735.  
  736.  
  737. /* Get next byte from file and update checksum */
  738.  
  739. int
  740. getc_crc(ib)
  741. FILE *ib;
  742. {
  743.     register c;
  744.  
  745.     c = getc(ib);
  746.     if(c != EOF)
  747.         crc += c;    /* checksum */
  748.     return c;
  749. }
  750.  
  751. /* Output functions with error reporting */
  752.  
  753. putce(c, iob)
  754. int c;
  755. register FILE *iob;
  756. {
  757.     if(putc(c, iob) == ERROR && ferror(iob)) {
  758.         fprintf(stderr, "sq:Write error\n");
  759.         exit(1);
  760.     }
  761. }
  762.  
  763. /*
  764.  * machine independent put-word that writes low order byte first
  765.  *  (compatible with CP/M original) regardless of host cpu.
  766.  */
  767. putwe(w, iob)
  768. register int w;
  769. register FILE *iob;
  770. {
  771.     putc(w, iob);
  772.     putc(w>>8, iob);
  773.     if (ferror(iob)) {
  774.         fprintf(stderr, "sq:Write error\n");
  775.         exit(1);
  776.     }
  777. }
  778.